﻿#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
//带环链表（判断是否带环：快慢指针  带环fast就可以追上slow）  
//bool hasCycle(struct ListNode* Head)
//{
//	struct ListNode* slow = head, * fast = head;    //slow   fast均指向头
//	while (fast && fast->next)
//	{
//		slow = slow->next;
//		fast = fast->next->next; 
//		if (slow == fast)   //最终找到相遇
//		{
//			return true;
//		}
//	}
//	return false;
//}

//问题一：为什么一定会相遇？会不会错过永远追不上？证明
//问题二：slow一次走两步  fast一次走三步  四步  五步  n步可以吗？   请证明
/*
	答1：当slow进环时  fast已经在环  假设相聚N  追击下去距离变化  从N递减到0（追击一次  距离缩小1  距离为0追上）

	答2：slow进环时  fast跟slow距离假设是N  追击过程距离变化N-2   N-4   N-6 ..... 6  4  0（偶数情况）
															N-2   N-4   N-6 ..... 3  1  -1（奇数情况）   会发生错过  然后开启新一轮追击
	距离变为C-1     C是环的长度（C-1是偶数 下一轮就追上）   若C-1为奇数（将会陷入死循环永远追不上）   N为距离差
	（这里的永远追不上的条件：C-1是奇数   N是奇数 （同时存在 C是偶数  N是奇数  那么就永远追不上）

	假设slow进环时fast跟slow距离是N   slow走的距离是：L   fast走的距离是：L+x*C+C-N
	slow进环   假设fast已经在环内走x圈    fast走的距离是slow的三倍
	3*L=L+x*C+C-N					N是奇数  C也是奇数
	2*L=（x+1）*C-N					N是偶数  C也是偶数
	同时存在 C是偶数  N是奇数  那么就永远追不上（故不能同时存在）   所以永远追不上的条件不存在
	故结论：一定能追上  N偶数第一圈就追上    N是奇数第一圈追不上  第二圈追上（是一定能追上）

	最终回归到步数差值（步数差值和环差的步数   讨论是否是步数差的倍数  是倍数可以追到   不是倍数追不上）   然后看最终差值进行讨论
*/


//环形链表2
//思路一
//给定链表头结点head  返回链表开始入环的第一个节点   链表无环  返回NULL，链表某节点可通过next再次到达  则存在环  找到环的入口点
//struct ListNode* detectCycle(struct ListNode* head)
//{
//    struct ListNode* slow = head, * fast = head;
//    while (fast && fast->next)
//    {
//        slow = slow->next;
//        fast = fast->next->next;
//        //相遇
//        if (slow == fast)
//        {
//            struct ListNode* meet = slow;
//            while (meet != head)
//            {
//                meet = meet->next;
//                head = head->next;
//            }
//            return meet;
//        }
//    }
//    return NULL;
//}

/*
	结论:一个指针从相遇点开始走（slow==fast）  一个指针从头（head）开始走   C为环的路程   x为走了几圈环
	假设头节点到环的入口点距离为L  相遇时slow在环中走了N   故相遇时slow走的路程：L+N    fast走的：L+x*C+N
	fast走的路程是slow的2倍
	故 2*(L+N)=L+x*C+N
	   L+N=x*C
	   L=x*C-N      x若为1  未走的路程就是C-N
	化简---->L=(x-1)*C+C-N
*/

//思路二：创建新节点  newhead   令newhead置为  newhead=meet->next;      meet->next=NULL;        转换为链表相交
//typedef struct ListNode ListNode;
//struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB)
//{
//    ListNode* pcurA = headA;
//    ListNode* pcurB = headB;
//    int countA = 0;
//    int countB = 0;
//    while (pcurA)
//    {
//        pcurA = pcurA->next;
//        countA++;
//    }
//    while (pcurB)
//    {
//        pcurB = pcurB->next;
//        countB++;
//    }
//    if (pcurA != pcurB)
//    {
//        return NULL;
//    }
//
//    int gap = abs(countA - countB);
//    //这是假设A长度值大于B长度值
//    ListNode* LongList = headA;
//    ListNode* ShortList = headB;
//    if (countA < countB)
//    {
//        LongList = headB;
//        ShortList = headA;
//    }
//    //后续就可以用长的链表先走gap步后再一起走判断是否相等   
//    while (gap--)
//    {
//        LongList = LongList->next;
//    }
//    while (LongList != ShortList)
//    {
//        LongList = LongList->next;
//        ShortList = ShortList->next;
//    }
//    return ShortList;
//}
//
//struct ListNode* detectCycle(struct ListNode* head)
//{
//    struct ListNode* slow = head, * fast = head;
//    while (fast && fast->next)
//    {
//        slow = slow->next;
//        fast = fast->next->next;
//        //相遇
//        if (slow == fast)
//        {
//            struct ListNode* meet = slow;
//            struct ListNode* newhead = meet->next;
//            meet->next = NULL;
//            return getIntersectionNode(head, newhead);
//        }
//    }
//    return NULL;
//}


//随机链表的复制
/*
	给一个长度n的链表  每个节点包含一个额外增加的随机指针random  该指针可以指向链表中的任何节点或空节点  
	 构造这个链表的深拷贝深拷贝应正好由n个全新节点组成  其中每个新节点的值都设为其对应的原节点的值 
	 新节点的next指针和random指针也都应该指向复制链表中的新节点
	 并使原链表和复制链表中的这些指针能够表示相同的链表状态  复制链表中的指针都不应指向原链表中的节点

	 拷贝链表：开辟链表节点 把开辟的节点进行赋值 后尾插到一起    
	 复杂点是：random

	 方法：1.开辟的新节点拷贝节点   把拷贝节点插入在原结点的后面   
		   2.新节点的random等于原节点random的next
		   3.再解开链表
*/

//struct Node {
//	int val;
//	struct Node* next;
//	struct Node* random;
//};
//
//struct Node* copyRandomList(struct Node* head) {
//    struct Node* cur = head;
//    // 拷贝节点  插入原节点后面
//    while (cur) {
//        struct Node* copy = (struct Node*)malloc(sizeof(struct Node));
//		if(copy==NULL)
//		{
//			return;
//		}
//        copy->val = cur->val;
//
//        copy->next = cur->next;
//        cur->next = copy;
//
//        cur = copy->next;
//    }
//
//    // 控制random
//    cur = head;
//    while (cur) {
//        struct Node* copy = cur->next;
//        if (cur->random == NULL) {
//            copy->random = NULL;
//        }
//        else {
//            copy->random = cur->random->next;
//        }
//        cur = copy->next;
//    }
//
//    // 拷贝节点取下来尾插成为新的链表   后恢复原链表
//    struct Node* copyhead = NULL, * copytail = NULL;
//    cur = head;
//    while (cur) {
//        struct Node* copy = cur->next;
//        struct Node* next = copy->next;
//
//        if (copytail == NULL) {
//            copyhead = copytail = copy;
//        }
//        else {
//            copytail->next = copy;
//            copytail = copytail->next;
//        }
//        cur->next = next;
//        cur = next;
//    }
//    return copyhead;
//}




//力扣  复杂链表拷贝
//#include <stdio.h>
//#include <stdlib.h>
//
//struct Node
//{
//	int val;
//	struct Node* next;
//	struct Node* random;
//};
//
//
//typedef struct Node Node;
//struct Node* copyRandomList(struct Node* head) {
//	Node* pcur = head;
//	// 拷贝节点
//	while (pcur) {
//		Node* next = pcur->next;
//		// 开辟新节点
//		Node* copynode = (Node*)malloc(sizeof(Node));
//		if (copynode == NULL)
//		{
//			return NULL;
//		}
//		// 开辟一个插入一个  cur的下一个指针赋给copynode下一个
//		copynode->val = pcur->val;
//		copynode->next = next;
//		pcur->next = copynode;
//		pcur = copynode->next;
//	}
//	// 处理random
//	pcur = head;
//	while (pcur) {
//		Node* copy = pcur->next;
//		if (pcur->random == NULL) {
//			copy->random = NULL;
//		}
//		else {
//			copy->random = pcur->random->next;
//		}
//		pcur = copy->next;
//	}
//
//	// 创一个新链表  把copy节点给拿出来  尾插成为一个新链表  返回头指针
//	pcur = head;
//	Node* newHead = NULL;
//	Node* newTail = NULL;
//	while (pcur) {
//		Node* newcopy = pcur->next;
//		Node* next = newcopy->next;
//		if (newTail == NULL) {
//			newHead = newTail = newcopy;
//		}
//		else {
//			newTail->next = newcopy;
//			newTail = newcopy;
//		}
//		pcur->next = next;
//		pcur = next;
//	}
//	return newHead;
//}
//
//int main()
//{
//	struct Node* node1 = (struct Node*)malloc(sizeof(struct Node));
//	struct Node* node2 = (struct Node*)malloc(sizeof(struct Node));
//	struct Node* node3 = (struct Node*)malloc(sizeof(struct Node));
//	struct Node* node4 = (struct Node*)malloc(sizeof(struct Node));
//	struct Node* node5 = (struct Node*)malloc(sizeof(struct Node));
//
//	node1->next = node2, node1->random = NULL, node1->val = 7;
//	node2->next = node3, node2->random = node1, node2->val = 13;
//	node3->next = node4, node3->random = node5, node3->val = 11;
//	node4->next = node5, node4->random = node3, node4->val = 10;
//	node5->next = NULL, node5->random = node1, node5->val = 1;
//
//	copyRandomList(node1);
//	return 0;
//}